/*
 * Package il.ac.biu.cs.grossmm.api.activeData
 * File BestConversionFinder.java
 * 
 * This is a part of presence service framework prototype. 
 * See javadoc for more information.
 *  
 * Copyright (C) 2006 Grossmann Mark
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.

 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */
package il.ac.biu.cs.grossmm.impl.activeData;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import il.ac.biu.cs.grossmm.api.flow.Converter;

/**
 * Filds all shortest conversion paths between all possible pairs of data
 * exchange points
 * 
 */
public class BestConversionChainFinder {
	// array of all data layers
	DataLayer[] dataLayers;

	// map from set of data layers to indeces of these layers
	// in the above array
	Map<DataLayer, Integer> indeces;

	/**
	 * Creates the new <tt>BestConversionChainFinder</tt> object based on data
	 * conversion graph
	 * 
	 * @param dataLayers
	 *            data layers
	 */
	BestConversionChainFinder(Collection<DataLayer> dataLayers) {
		int size = dataLayers.size();

		this.dataLayers = new DataLayer[size];
		indeces = new HashMap<DataLayer, Integer>(size);

		// for all data layers
		int i = 0;
		for (Iterator it = dataLayers.iterator(); it.hasNext();) {
			DataLayer dataLayer = (DataLayer) it.next();

			// put the layer to the array
			this.dataLayers[i] = dataLayer;

			// remember the index
			indeces.put(dataLayer, i);

			i++;
		}
	}

	@SuppressWarnings("unchecked")
	void findBestChains() {
		int n = dataLayers.length;
		int i, j, k;

		// emulation of 2-dimentional arrays of priorities and predcessors
		// (emulation is used for optimization)
		double[] priorities = new double[n * n];
		int[] predcessor = new int[n * n];

		// initialize priorities
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++) {
				int ij = i * n + j;
				if (i == j) {
					// same vertex (data layer)
					priorities[ij] = 0;
					predcessor[ij] = -1;
				} else {
					// priority of direct conversino from layer i to layer j
					double priority = getDirectPriority(i, j);
					priorities[ij] = priority;

					if (priority == 0)
						predcessor[ij] = -1; // hm?
					else
						predcessor[ij] = i;
				}
			}

		// dynamically compute matrices of priorities and predcessors
		for (k = 0; k < n; k++) {
			for (i = 0; i < n; i++) {
				for (j = 0; j < n; j++) {
					int ij = i * n + j, ik = i * n + k, kj = k * n + j;

					// priotity of current chain i~>j
					double priority = priorities[ij];

					// priority of chain i~>k~>j
					double priority2 = priorities[ik] * priorities[kj];

					// is the second priority a better choice?
					if (priority < priority2) {
						// select a new chain

						// update priority
						priorities[ij] = priority2;

						// update predcessor of j
						predcessor[ij] = predcessor[kj];
					}
				}
			}
		}

		Converter[] a = new Converter[n];

		// extract shortest chains
		for (j = 0; j < n; j++) {
			// extract best chains from the j-th data layer to all the rest

			Map<DataLayer, ConversionChain> bestChains = new HashMap<DataLayer, ConversionChain>();

			for (i = 0; i < n; i++) {
				// extract a best chain from the i-th data layer to data the
				// layer j
				if (i == j)
					continue; // short path

				// put
				int index = n;

				k = j;

				while (true) {
					int k_prev = k;
					k = predcessor[i * n + k];

					assert k != k_prev : "Loop!";

					if (k == -1)
						break;

					a[--index] = dataLayers[k]
							.getConverterTo(dataLayers[k_prev]);
				}

				int length = n - index;

				if (length == 0)
					continue;

				ConversionProcessor[] chain = new ConversionProcessor[length];
				System.arraycopy(a, index, chain, 0, length);

				double priority = priorities[i * n + j];

				ConversionChain cc = new ConversionChain(chain, priority);

				// add best chain from layer [i] to layer [j]
				bestChains.put(dataLayers[i], cc);
			}

			dataLayers[j].setConversionChains(bestChains);
		}
	}

	/**
	 * Gets the relative priority of conversion from i-th data layer to j-th
	 * data layer. Returns zero if there is no unconditional converter to
	 * convert between the layers
	 * 
	 * @param i
	 * @param j
	 * @return relative priority of conversion from i-th data layer to k-th data
	 *         layer, or zero if there is no unconditional converter to convert
	 *         between the layers
	 */
	private double getDirectPriority(int i, int j) {
		// get the layers
		DataLayer from = dataLayers[i];
		DataLayer to = dataLayers[j];
		
		// get converter to convert from from i-th data layer to j-th
		// data layer
		Converter c = from.getConverterTo(to);

		// return zero if no such converter
		if (c == null)
			return 0;

		// return the priority
		return c.getPriority();
	}

}
